package chapter2;

/**
 * @author Hang
 * @date 2022/8/10
 * @project AutumnOffer
 * @description 面试题12
 **/
public class exist {
    public static void main(String[] args) {
        char[][] b = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String s = new String("SEE");
        System.out.println(exist(b,s));
    }
    public static boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray(); //数组
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(dfs(i,j,0,board,words)) return true; // 扫描判断
            }
        }
        return false;
    }
    public static boolean dfs(int i,int j,int k,char[][] board,char[] words){
        if(i>=board.length||i<0||j>=board[0].length||j<0||board[i][j] != words[k]){
            return false; //不匹配条件
        }
        if(k == words.length - 1){//找到了
            return true;
        }
        board[i][j] = '\0';//避免重复访问同一个元素
        boolean res = dfs(i-1,j,k+1,board,words)||dfs(i+1,j,k+1,board,words)||
                dfs(i,j-1,k+1,board,words)||dfs(i,j+1,k+1,board,words); // 深度搜索
        board[i][j] = words[k]; // 回溯
        return res;
    }
}
